home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 142 / Gekkan Dennou Club - 2000.3 Vol. 142 (Japan).7z / Gekkan Dennou Club - 2000.3 Vol. 142 (Japan) (Track 1).bin / docs / perl / bintree.pm next >
Text File  |  2000-01-23  |  1KB  |  63 lines
  1. #
  2. # Bintree.pm : 二分探索木（オブジェクトのテスト）
  3. #
  4. # 格納するデータはオブジェクトであること
  5. #
  6. package Bintree;
  7.  
  8. # 終端を示す nil 用無名空ハッシュ
  9. $nil = {};
  10. bless $nil, 'Bintree';
  11.  
  12. # 二分木を空に初期化
  13. sub make_tree { $nil; }
  14.  
  15. # 二分木の探索
  16. sub search_tree {
  17.   my ($node, $item) = @_;
  18.   while( $node != $nil ){
  19.     my $result = $item->compare( $node->{'item'} );
  20.     if( $result == 0 ){
  21.       return 1;
  22.     } elsif( $result < 0 ){
  23.       $node = $node->{'left'};
  24.     } else {
  25.       $node = $node->{'right'};
  26.     }
  27.   }
  28.   0;
  29. }
  30.   
  31. # データの追加
  32. sub insert_tree {
  33.   my ($node, $item) = @_;
  34.   if( $node == $nil ){
  35.     my $new = {'item' => $item, 'left' => $nil, 'right' => $nil };
  36.     bless $new, 'Bintree';
  37.     return $new;
  38.   } else {
  39.     my $result = $item->compare( $node->{'item'} );
  40.     if( $result < 0 ){
  41.       $node->{'left'} = &insert_tree( $node->{'left'}, $item );
  42.     } elsif( $result > 0 ){
  43.       $node->{'right'} = &insert_tree( $node->{'right'}, $item );
  44.     }
  45.   }
  46.   $node;
  47. }
  48.  
  49. # 二分木の表示
  50. sub print_tree {
  51.   my $node = shift;
  52.   if( $node != $nil ){
  53.     &print_tree( $node->{'left'} );
  54.     $node->{'item'}->print_object();
  55.     &print_tree( $node->{'right'} );
  56.   }
  57. }
  58.  
  59. 1;
  60.  
  61. # end of file
  62.  
  63.